package com.leetcode.algs4.string;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Dennis Li
 * @date 2020/7/9 22:53
 */
public class KMP {

    private static final List<Integer> matches = new ArrayList<>();

    public static int[] prefixTable(String pattern) {

        char[] array = pattern.toCharArray();
        int n = array.length;
        int[] prefix = new int[n];
        prefix[0] = 0;

        // len 表示公共前后缀长度
        int len = 0, i = 1;
        while (i < n) {
            if (array[i] == array[len]) {
                len++;
                prefix[i] = len;
                i++;
            } else {
                if (len > 0) {
                    // 斜着对应
                    // len的值替换为前一位的后缀长度
                    len = prefix[len - 1];
                } else {
                    // i一开始会出现死循环，第一位要置为0，然后i++退出死循环
                    prefix[i] = len;
                    // i++退出循环
                    i++;
                }
            }
        }
        return prefix;
    }

    public static void movePrefixTable(int[] prefix) {
        for (int i = prefix.length - 1; i > 0; i--) {
            prefix[i] = prefix[i - 1];
        }
        prefix[0] = -1;
    }

    public static void kmpSearch(String text, String pattern) {
        // 定义前缀表
        int[] prefix = prefixTable(pattern);
        movePrefixTable(prefix);

        char[] t = text.toCharArray();
        char[] p = pattern.toCharArray();

        int m = t.length, n = p.length;
        // i是母串的游标，j是模式串的游标
        int i = 0, j = 0;

        while (i < m) {
            // 当模式串到达末尾且此时与对应母串的字符相等，代表找到了子串
            if (j == n - 1 && t[i] == p[j]) {
                System.out.println("Found pattern at " + (i - j));
                // 将所有匹配的串的开始位置加入到列表中
                matches.add(i - j);
                // 找到一个不代表找完，还会继续查找
                j = prefix[j];
            }
            // 相等，那么两个游标都向右移动
            if (t[i] == p[j]) {
                i++;
                j++;
            } else {
                // 如果不相等，模式串的游标进行回退操作，根据前缀表进行回退
                // 这个时候母串的游标不移动
                j = prefix[j];
                // 当模式串退到首位时，i、j两者都要+1，这样会j到了0位
                // 模式串整体向右移动一位
                if (j == -1) {
                    i++;
                    j++;
                }
            }
        }

    }

    public static void main(String[] args) {
        String pattern = "ABA";
        String text = "ABAABAABAABC";
        kmpSearch(text, pattern);
        matches.forEach(i -> System.out.print(i + " "));
    }

}
